package leetcode.editor.cn;
//2021-08-05 10:10:03	获取当前时间
//给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
//
// 如果 s 中存在多个符合条件的子字符串，返回任意一个。
//
//
//
// 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//
//
//
// 示例 1：
//
//
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
//
// 示例 2：
//
//
//输入：s = "a", t = "a"
//输出："a"
//
//
// 示例 3：
//
//
//输入：s = "a", t = "aa"
//输出：""
//解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
//
//
//
// 提示：
//
//
// 1 <= s.length, t.length <= 105
// s 和 t 由英文字母组成
//
//
//
//
// 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
//
//
//
// 注意：本题与主站 76 题相似（本题答案不唯一）：https://leetcode-cn.com/problems/minimum-window-subs
//tring/
// Related Topics 哈希表 字符串 滑动窗口
// 👍 0 👎 0


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution_offer__017 {
    public String minWindow(String s, String t) {
        List<String> list = new ArrayList();
        while(!"".equals(targetStr(s, t))) {
            String target = targetStr(s, t);
            list.add(target);
            s = s.substring(s.indexOf(target) + 1);
        }
        if(list.size() == 0) {
            return "";
        }
        int length = 0;
        String result = "";
        for (int i = 0; i < list.size(); i++) {
            int strLen = list.get(i).length();
            if(i == 0) {
                length = strLen;
                result = list.get(i);
            } else {
                if(length > strLen) {
                    length = strLen;
                    result = list.get(i);
                }
            }
        }
        return result;
    }
    public String targetStr(String s, String t) {
        //如果s或是t为null，直接返回空字符串
        if(s == null || t == null) {
            return "";
        }
        //如果t的长度大于s的长度返回空字符串
        if(t.length() > s.length()) {
            return "";
        }
        //两个字符串一样，返回t
        if(t != null && t.equals(s)) {
            return t;
        }
        //s包含t的所有字符，返回包含t所有字符的最短子字符串。
        int max = 0;
//        int max1 = 0;
        int min = 0;
//        int min1 = 0;
        Map<String, Integer> map = new HashMap();
        for (int i = 0; i < t.length(); i++) {
            //获取t的第i个字符
            String c = t.substring(i, i+1);
//            int lastIndex = s.lastIndexOf(c);
            int index = s.indexOf(c);
            if (map.containsKey(c)) {
//                lastIndex = s.lastIndexOf(c, lastIndex -1);
                index = s.indexOf(c, map.get(c) + 1);
                map.put(c, index);
            } else {
                map.put(c, index);
            }
            //s不包含t的所有字符，返回空字符串
            if(index == -1) {
                return "";
            }
            //s获取包含t所有字符的最大最小的角标
            if(i == 0) {
                max = index;
//                max1 = lastIndex;
                min = index;
//                min1 = lastIndex;
            }
            if(index < min) {
                min = index;
            } else if(index >= max) {
                max = index;
            }
//            if(lastIndex < min1) {
//                min1 = lastIndex;
//            } else if(lastIndex >= max1) {
//                max1 = lastIndex;
//            }
        }
//        String subStr1 = s.substring(min1, max1 + 1);
        String substr = s.substring(min, max + 1);
//        if(subStr1.length() > substr2.length()) {
//            return substr2;
//        }
        return substr;
    }

    public static void main(String[] args) {
        Solution_offer__017 solutionOffer017 = new Solution_offer__017();
        String s = solutionOffer017.minWindow("aaflslflsldkalskaaa", "aaa");
        System.out.println("s = " + s);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
